package DynamicProgrammingPackage;

public class PackageNote {
    public static void main(String[] args) {
        //          重量 价值
        // 物品0      1   15
        // 物品1      3   20
        // 物品2      5   30
        // int[] weight = new int[]{1,2,3};
        // int[] value = new int[]{15,20,30};
        // 1. dp[i][j] 表示 从物品0 - 物品i中任取物品撞到容量为j的背包中,其价值为dp[i][j]
        // 2. 递推公式: 取不装物品i 和 装物品i 得到的价值最大值
        // dp[i][j] = Math.Max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i])
        // 3. 初始化:
        //      j  0    1   2   3   4
        // i
        // 物品0    0   15  15  15  15
        // 物品1    0  任意 任意 任意 任意
        // 物品2    0  任意 任意 任意 任意
        // 我们发现, 非零下标的dp[i][j]都可以由上方或左上方推出来, 故我们需要初始化最上端一行和最左一列数据
        // 最左一列数据初始化为0, 因为背包容量为0时, 其价值为0
        // 最上端一行数据, 根据背包容量和物品0的价值来初始化, 如1,2,3,4容量均可容纳物品0, 则初始化为物品0的价值
        // 4. 遍历顺序
        // 第一层遍历物品, 第二层遍历背包即 先从左到右遍历, 再从上到下遍历. 这样满足递推公式

        int[][] dp = new int[3][5];
        int[] weight = new int[]{1,3,5};
        int[] value = new int[]{15,20,35};
        for (int i = 0; i < 3; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j < 5; j++) {
            if (j >= weight[0]){
                dp[0][j] = value[0];
            }
            else {
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < 3; i++) {
            for (int j = 1; j < 5; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i - 1][j-weight[i]] + value[i]);
            }
        }

        // 一维dp数组的背包问题
    }
}
